public class Knapsack {
    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        // 背包问题
        // dp[i][j]表示在前i个物品中选择装入背包，使得背包容量不超过j是的最大重量
        // 如果当前背包剩下的容量能够装下第i个物品，那么
        // dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-vm[i][0]]_vw[i][1])
        // 如果当前背包容量无法装下第i个物品，那么dp[i][j] = dp[i-1][j]
        int[][] dp = new int[n+1][V+1];
        // 初始化dp[0][j]表示从前0个物品中选择装入，使得不超过背包容量j时的最大重量，dp[0][j]=0
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= vw[i-1][0]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-vw[i-1][0]] + vw[i-1][1]);
                }
            }
        }
        return dp[n][V];
    }

    public int knapsack1 (int V, int n, int[][] vw) {
        // write code here
        // 背包问题
        // 空间优化，填dp[i][j]的时候只需要依赖dp[i-1]行
        // dp[i-1][j] dp[i-1][j-vw[i-1][0]]
        // 可以将空间优化为一维数组
        // 然后填表顺序是从上往下、从右往左
        int[] dp = new int[V+1];
        for (int i = 1; i <= n; i++) {
            for (int j = V; j >= vw[i-1][0]; j--) {
                dp[j] = Math.max(dp[j], dp[j-vw[i-1][0]] + vw[i-1][1]);
            }
        }
        return dp[V];
    }
}
